home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / langs / iconv8_l.arc / PROGS.ARC / recgen.icn < prev    next >
Encoding:
Text File  |  1990-03-08  |  2.1 KB  |  84 lines
  1. ############################################################################
  2. #
  3. #    Name:    recgen.icn
  4. #
  5. #    Title:    Generate recognizer for sentences in a context-free language
  6. #
  7. #    Author:    Ralph E. Griswold
  8. #
  9. #    Date:    June 10, 1988
  10. #
  11. ############################################################################
  12. #
  13. #     This program reads a context-free grammar and produces an Icon
  14. #  program that is a recognizer for the corresponding language.
  15. #
  16. #     Nonterminal symbols are represented by uppercase letters. Vertical
  17. #  bars separate alternatives.  All other characters are considered to
  18. #  be terminal symbols.  The nonterminal symbol on the last line is
  19. #  taken to be the goal.
  20. #
  21. #     An example is:
  22. #
  23. #    X::=T|T+X
  24. #    T::=E|E*T
  25. #    E::=x|y|z|(X)
  26. #
  27. #  Limitations:
  28. #
  29. #     Left recursion in the grammar may cause the recognizer to loop.
  30. #  There is no check that all nonterminal symbols that are referenced
  31. #  are defined.
  32. #
  33. #  Reference:
  34. #
  35. #     The Icon Programming Language, Ralph E. and Madge T. Griswold,
  36. #  Prentice-Hall, 1983. pp. 161-165.
  37. #
  38. ############################################################################
  39.  
  40. global goal
  41.  
  42. procedure main()
  43.    local line, sym
  44.  
  45.    while line := read() do define(line)
  46.    write("\nprocedure main()")
  47.    write("   while line := read() do {")
  48.    write("      writes(image(line))")
  49.    write("      if line ? (",goal,"() & pos(0)) then _
  50.       write(\": accepted\")\n      else write(\": rejected\")")
  51.    write("      }")
  52.    write("end")
  53. end
  54.  
  55. procedure expand(s,x)
  56.    local s1, sym
  57.  
  58.    s1 := ""
  59.    s ? while sym := move(1) do
  60.       if any(&ucase,sym) then s1 ||:= sym || "() || "
  61.       else s1 ||:= "=\"" || sym || "\" || "
  62.    return s1[1:-4]
  63. end
  64.  
  65. procedure define(line)
  66.    line ? (
  67.       write("\nprocedure ",goal := move(1),"()"),
  68.       ="::=",
  69.       write("   suspend {"),
  70.       (every write("      ",prodlist())) | "",
  71.       write("      }"),
  72.       write("end")
  73.       )
  74. end
  75.  
  76. procedure prodlist()
  77.    local p
  78.    while p := expand(tab(many(~'|')),"=") do {
  79.       move(1) | return "(" || p || ")"  # last alternative
  80.       suspend "(" || p || ") |"
  81.       }
  82. end
  83.  
  84.